// 动态规划

#include <string.h>

#include <iostream>
#include <vector>
using std::cout;
using std::endl;

// 搜索引擎或输入法的智能纠错。
/*
如何量化两个字符串的相似度？编辑距离

1.莱文斯坦距离允许增加、删除、替换字符这三个编辑操作。莱文斯坦距离越小，两个字符串越相似
m    t a c n  u
m i- t + c m* u
莱文斯坦距离是3

      m t a c n u
i=0 m 0 1 2 3 4 5
i=1 i 1 1 2 3 4 5
    t 2 1 2 3 4 5
    c 3 2 2 2 3 4
    m 4 2 3 3 3 4
    u 5 4 4 4 4 3

if (source[j] != pattern[i])
  minDist[i][j] = Min(minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1]+1);
if (source[j] == pattern[i])
  minDist[i][j] = Min(minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1]);

2.最长公共子串长度只允许增加、删除字符这两个编辑操作。最长公共子串长度越大，两个字符串越相似
m   t a c n u
m i t   c m u
最长公共子串长度是4
*/

int Min(int a, int b, int c) { return std::min(std::min(a, b), c); }

// 求两个字符串的相似度？利用莱文斯坦距离求解
int lwstDP(const char* source, const char* pattern) {
  int sourceLen = strlen(source);
  int patternLen = strlen(pattern);
  std::vector<std::vector<int>> minDist(patternLen);
  for (int i = 0; i < minDist.size(); ++i) {
    minDist[i].resize(sourceLen);
  }

  int first = source[0] == pattern[0] ? 0 : 1;
  for (int i = 0; i < patternLen; ++i) {
    for (int j = 0; j < sourceLen; ++j) {
      if (i == 0 || j == 0) {
        if (i == 0) minDist[i][j] = j + first;
        if (j == 0) minDist[i][j] = i + first;
      } else {
        if (source[j] != pattern[i]) {
          minDist[i][j] = Min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1,
                              minDist[i - 1][j - 1] + 1);
        } else {
          minDist[i][j] = Min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1,
                              minDist[i - 1][j - 1]);
        }
      }
    }
  }

  return minDist[minDist.size() - 1][minDist[0].size() - 1];
}

void TestlwstDP() { cout << "lwstDist:" << lwstDP("mtacnu", "mitcm") << endl; }

int main() { TestlwstDP(); }